public class Test35 {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean dp[][] = new boolean[n][n];
        int ret = 0;
        for(int i = n - 1;i >= 0;i--) {
            for(int j = i;j < n;j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = j - i < 2 ?  true : dp[i + 1][j - 1];
                }
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }

    // 自己写的
    //     int n = s.length();
    //     int[] dp = new int[n];
    //     int count = 1;
    //     for(int i =0;i < n;i++) dp[i] = 1;
    //     for(int i = 1;i < n;i++) {
    //         for(int j = 0;j < i;j++) {
    //             String str = s.substring(j,i + 1);
    //             if(isPalindrome(str)) {
    //                 dp[i] += 1;
    //             }
    //         }
    //         count += dp[i];
    //     }
    //     return count;
    // }
    // public Boolean isPalindrome(String s) {
    //     if(s.length() == 1) return true;
    //     int k = s.length() / 2;
    //     int l = 0;
    //     int r = s.length() - 1;
    //     while (k > 0) {
    //         if(s.charAt(l) == s.charAt(r)) {
    //             l++;
    //             r--;
    //         }
    //         else return false;
    //         k--;
    //     }
    //     return true;
    // }
}
